package com.wn.date20190813.stack;

import java.util.Iterator;

/**
 * 扩展:实现数据结构-栈：Stack
 * 
 * public class Stack{ private Object[] data; private int size; public Stack(){}
 * public Stack(int num){} 
 * public void push(Object o){} 
 * public Object pop(){} }
 * peek（）{}查看栈顶
 * @author song
 *
 */
public class Stack implements Iterable<Object>
{
	private static final int initalCapacity=5;
	private Object[] data;
	private int size = 0;
	
	public Stack(int num)
	{
		data = new Object[initalCapacity];
	}

	public Stack()
	{
		data = new Object[5];
	}
	/**
	 * 清除
	 */
	public void clear()
	{
		size=0;
		data=new Object[initalCapacity];
	}
	/**
	 * 查看栈顶
	 * @return
	 */
	public Object peek()
	{
		return data[size-1];
	}
	/**
	 * 查看size
	 * @return
	 */
	public int size()
	{
		return size;
	}
	/**
	 * 出栈
	 * @return
	 * @throws Exception 
	 */
	public Object pop() throws Exception
	{
		Object obj;
		if(size>0)
		{
			obj=data[size-1];
			// 缩短
			narrow(1);
		}else {
			throw new Exception();
		}
		return obj;
	}
	// 缩小数组
	private void narrow(int i)
	{
		// 缩小到刚好满
		Object[] shortObjects=new Object[size-i];
		System.arraycopy(data, 0, shortObjects, 0, shortObjects.length);
		size-=i;
		data=shortObjects;
		shortObjects=null;
	}

	/**
	 * 入栈
	 * @param obj
	 * @return
	 */
	public boolean push(Object obj)
	{
		if(data.length==size)
		{
			// 扩容
			grow(size+1);
		}
		data[size++] = obj;
		return true;
	}
	/**
	 * 批量入栈
	 * @param objs
	 * @return
	 */
	public boolean pushAll(Object[] objs)
	{
		// 判空
		if(objs==null||objs.length==0)
		{
			return false;
		}
		if(data.length-size<objs.length)
		{
			// 扩容
			grow(size+objs.length);
		}
		for(Object o:objs)
		{
			data[size++]=o;
		}
		return true;
	}

	/**
	 * 扩容 最小长度
	 * @param minLength
	 */
	private void grow(int minLength)
	{
		int newLength=data.length+data.length>>1;// 扩容为1.5
		if(newLength-minLength<0)
		{
			newLength=minLength;
		}
		Object[] plus = new Object[newLength];
		System.arraycopy(data, 0, plus, 0, data.length);
		data = plus;
		plus = null;
	}

	@Override
	public Iterator<Object> iterator()
	{
		return new Iterator<Object>(){
			int count=0;
			@Override
			public boolean hasNext()
			{
				return size>count;
			}

			@Override
			public Object next()
			{
				return data[count++];
			}
			
		};
	}


}
